package com.heima.leetcode.algorithm.sort;

/**
 * <strong>根据另一个数组次序排序当前数组 1122</strong>
 * <p>两个数组满足条件：另一个数组是当前数组的子集</p>
 * <p>两个数组的元素值均 >= 0 <= 1000(从这里其实可以看出多半用计数排序解题)</p>
 * <p>两个数组长度 <= 1000</p>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/6 22:15
 */
public class RelativeSortArray {

    /**
     * 数组的相对排序 1122
     * @param arr1 数组一
     * @param arr2 数组2
     * @return 数组1排序后的结果
     */
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        // 创建1001长度的计数数组，用来记录arr1中每个元素出现的次数
        int[] count = new int[1001];
        // 创建result数组，用来存储排序后的结果
        int[] result = new int[arr1.length];
        // 遍历arr1，记录每个元素出现的次数
        for (int i : arr1) {
            count[i]++;
        }
        // 遍历arr2，以arr2遍历到的元素作为count数组的索引去查询arr1中该元素出现的次数，根据次数加入新元素到result数组中，取完要保证count[index]处值为0
        int index = 0;
        for (int i : arr2) {
            while (count[i] > 0){
                result[index++] = i;
                count[i]--;
            }
        }
        // count数组剩余的就是剩下没重复的，就按计数排序正常来
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0){
                result[index++] = i;
                count[i]--;
            }
        }
        // 返回排序后的结果
        return result;
    }
}
